Expert systems are generally employed by applying an inference engine to a knowledge base. Two popular methods used in expert systems are forward chaining and backward chaining.
Forward chaining refers to the process of testing rules against known facts in a knowledge base. A rule consists of one or more conditions and an action. If the conditions are met, the inference engine may fire the rule. An example of a rule might be, “if A>10, then B=10.” The knowledge base consists of facts representing objects with assigned values, e.g. “A=20.” The knowledge base may also contain rules. Forward chaining generally compares each fact with each rule to create a list of rules that may be fired. For the examples above, comparing the knowledge base with the rules would reveal that the rule could be fired. If multiple rules could be fired, the expert system usually includes a method for determining which rule has priority, because the order of firing can alter the results found by the expert system. Since there is no other rule to fire for the example rule and fact, it would fire and the knowledge base would be expanded to include “B=10.”
Forward chaining is a very effective and widely used strategy. Integration of a wide variety of systems and sources of information allow access to large knowledge bases, increasing the power of forward chaining. However, large knowledge bases and rule sets increase the need for improved computational power and organization. Forward chaining is not effective in solving all problems. Some problems, such as diagnostics, are more suitable to solving by backward chaining.
One well known and efficient version of forward chaining is a RETE network. A RETE network achieves improved performance over the standard forward chaining algorithm because it creates a tree that links conditions, partial conditions and rules in a way that can be reused. Using this structure, the expert system no longer requires the comparison of each object in the knowledge base against each condition of every rule. Instead, only changes in the knowledge base need to be tested.
Forward chaining is not effective in solving all problems. Some problems, such as diagnostics, are more suitable to solving by backward chaining. Backward chaining uses the same knowledge base and rule set, but operates as a depth first search working from the rules to the conditions. Backward chaining begins by examining goals. For example, a goal may be “?B.” The backward chaining system looks at each rule, and finds the set of rules that have an action that produces a value for B. Using the same example rule as above, the system would see that the rule produces a value for B. The next step would be to test the conditions of the rule that provides a value for the goal. The example rule has the condition “A>10.” By comparing this condition to the knowledge base, the system finds that there is a value assigned to the object A, and it is greater than 10. The inference engine would then fire the rule, solving the stated goal.
Neither forward chaining nor backward chaining is the most efficient technique in every situation. For this reason, some attempts have been made to combine forward chaining and backward chaining systems. By developing a mixed mode inferencing system that has either method at its disposal, the system can use the method best suited to a particular problem to solve a wider variety of problems in a more efficient manner. However, prior attempts to combine these methods have not been able to develop a structure that allows the expert system to operate efficiently in the backward chaining inference mode in a manner similar to the RETE network that is often employed in forward chaining.
One prior system attempts to integrate forward chaining or backward chaining in a mixed or hybrid chaining approach. The approaches for both forward chaining (FC) and backward chaining (BC) follow existing techniques, FC using Rete, BC using stack based depth-first traversal and matching. They are merged in an integrated fashion. When objects are distributed to the Rete network, rule instances may enter the conflict set. If an inference engine device detects the existence of a rule instance in the conflict set, it suspends backward chaining reasoning at that point and allows the rule to be activated. When a rule is activated, it is deleted from a goal stack.
Such an approach does not address maintaining integrity of the network. More particularly, a changed status of working memory can't be tracked which may lead to failure of the inference engine as the “backward chain” progresses across the network. In any event, it should be apparent that rule activation happens as a side effect. No selective firing of the rules is attempted.